package com.dreamfire.ai.path.astar
{
	import flash.geom.Point;
	
	public class Path
	{
		public static const MANHATTAN:int = 0;
		
		private static const COST_STRAIGHT:int = 10;//垂直\水平移动一格的消耗
		private static const COST_DIAGONAL:int = 14;//斜向移动一格的消耗
		
		private static var open:Vector.<Node>;
		private static var close:Vector.<Node>;
		private static var beginNode:Node;
		private static var targetNode:Node;
		
		private static var mapWidth:int;
		private static var mapHeight:int;
		
		private static var _mapData:Array;
		private static var _maxAttempt:uint;
		private static var _available:int = 1;
		private static var _targetPointVec:Vector.<Point>;
		
		/**
		 * 从顶部开始,顺时针方向一圈
		 */
		private static var aroundList:Array = [[-1, -1], [-1, 0], [-1, 1], [0, 1], [1, 1], [1, 0], [1, -1], [0, -1]];
		
		public static function searchPath(beginPoint:Point, targetPoint:Vector.<Point>, mapData:Array):Vector.<Point>
		{
			_targetPointVec = targetPoint;
			var tp:Point = _targetPointVec[0];
			init();
			beginNode = new Node(beginPoint.x, beginPoint.y);
			targetNode = new Node(tp.x, tp.y);
			beginNode.f = heuristic(beginNode);
			beginNode.g = 0;
			beginNode.h = beginNode.f;
			open.push(beginNode);
			_mapData = mapData;
			mapHeight = (_mapData[0] as Array).length;
			mapWidth = _mapData.length;
			
			var attempts:int = 0;
			var currentNode:Node;
			var aroundNode:Vector.<Node>;
			var needSort:Boolean;
			while(open.length > 0)
			{
				if(_maxAttempt > 0)
				{
					if(attempts >= _maxAttempt)
					{
						return null;
					}
				}
				currentNode = open.shift();
				close.push(currentNode);
				for each (var k:Point in _targetPointVec) 
				{
					if(currentNode.x == k.x && currentNode.y == k.y)
					{
						return makePath(currentNode);
					}
				}
				aroundNode = getAround(currentNode);
				needSort = false;
				for each(var i:Node in aroundNode)
				{
					var openIndex:int = isOpen(i);
					if(openIndex >= 0)
					{
						if(open[openIndex].h > i.h)
						{
							open[openIndex].h = i.h;
							open[openIndex].g = i.g;
							open[openIndex].f = i.f;
							open[openIndex].parent = i.parent;
						}
					}else{
						needSort = true;
						open.push(i);
					}
				}
				if (needSort){
					open = open.sort(sortNode);
				}
				attempts++;
			}
			return null;
		}
		private static function init():void
		{
			open = new Vector.<Node>();
			close = new Vector.<Node>();
			beginNode = null;
			targetNode = null;
			mapWidth = 0;
			mapHeight = 0;
			_mapData = null;
		}
		public static function set availableCode(value:int):void
		{
			_available = value;
		}
		
		public static function get availableCode():int
		{
			return _available;
		}
		
		public static function set max(value:uint):void
		{
			_maxAttempt = value;
		}
		
		public static function get max():uint
		{
			return _maxAttempt;
		}
		private static function sortNode(x:Node, y:Node):Number
		{
			if(x.h < y.h)
			{
				return -1;
			}else if(x.h > y.h){
				return 1;
			}else{
				return 0;
			}
		}
		
		private static function heuristic(node:Node, type:int = 0):int
		{
			var cost:int = 0;
			if(MANHATTAN == type)
			{
				cost = manhattan(node);
			}
			return cost;
		}
		
		private static function manhattan(node:Node):int
		{
			var c:int = (Math.abs(targetNode.x - node.x) + Math.abs(targetNode.y - node.y)) * COST_STRAIGHT;
			return c;
		}
		private static function isOpen(node:Node):int
		{
			for(var i:* in open) 
			{
				if(node.x == open[i].x && node.y == open[i].y)
				{
					return int(i);
				}
			}
			return -1;
		}
		
		private static function isClose(node:Node):int
		{
			for(var i:* in close) 
			{
				if(node.x == close[i].x && node.y == close[i].y)
				{
					return int(i);
				}
			}
			return -1;
		}
		
		private static function getAround(node:Node):Vector.<Node>
		{
			var around:Vector.<Node> = new Vector.<Node>();
			for(var i:int = 0; i < 8; i++)
			{
				var nx:int = node.x + aroundList[i][0];
				var ny:int = node.y + aroundList[i][1];
				if(nx >= 0 && nx < mapWidth && ny >= 0 && ny < mapHeight)
				{
					if(_mapData[nx][ny] == _available)
					{
						var n:Node = new Node(nx, ny);
						if(isClose(n) >= 0){
							continue;
						}
						var pc:int = COST_DIAGONAL;
						
						switch(i)
						{
							case 0:
							{
								if (nx + 1 < mapWidth && ny + 1 < mapHeight){
									if(_mapData[nx + 1][ny] != _available || _mapData[nx][ny + 1] != _available)
										continue;
								}
								break;
							}
							case 2:
							{
								if (nx + 1 < mapWidth && ny - 1 >= 0){
									if(_mapData[nx + 1][ny] != _available || _mapData[nx][ny - 1] != _available)
										continue;
								}
								break;
							}
							case 4:
							{
								if (nx - 1 >= 0 && ny - 1 >= 0){
									if(_mapData[nx - 1][ny] != _available || _mapData[nx][ny - 1] != _available)
										continue;
								}
								
								break;
							}
							case 6:
							{
								if (nx - 1 >= 0 && ny + 1 < mapHeight){
									if(_mapData[nx - 1][ny] != _available || _mapData[nx][ny + 1] != _available)
										continue;
								}
								break;
							}
							default:
							{
								pc = COST_STRAIGHT;
								break;
							}
						}
						n.parent = node;
						n.g = n.parent.g + pc;
						n.f = heuristic(n);
						n.h = n.g + n.f;
						around.push(n);
					}
				}
			}
			return around;
		}
		
		private static function makePath(n:Node):Vector.<Point>
		{
			var pathList:Vector.<Point> = new Vector.<Point>();
			while(true)
			{
				if(n.x == beginNode.x && n.y == beginNode.y)
				{
					return pathList;
				}
				var p:Point = new Point(n.x, n.y);
				pathList.push(p);
				n = n.parent;
			}
			return null;
		}
	}
}